package huawei;

import java.util.*;

/**
 * 二叉树的计算
 */
public class Q92 {

    public static class Node{
        Node left;
        Node right;
        int val;

        public Node(int val){
            this.val = val;
        }
    }

//    static int[] pre = {6,7,-2,9,6};
//    static int[] mid = {7,-2,6,6,9};

    static int[] pre = {8, 12, -3, 6, -10, 9, -7};
    static int[] mid = {-3, 12, 6, 8, 9, -10, -7};

    public static void main(String[] args) {

        Node root = build(0, 0, mid.length - 1);
        System.out.println(root);
        StringBuilder psb = new StringBuilder();
        StringBuilder msb = new StringBuilder();

        dfsM(root, msb);
        System.out.println(msb);

        dfsP(root, psb);
        System.out.println(psb);

        Node newRoot = copyTree(root);
        System.out.println(newRoot);
    }
    // 钱序遍历
    public static void dfsP (Node root, StringBuilder sb){
        if(root == null){return;}
        sb.append(root.val);
        sb.append(' ');
        dfsP(root.left, sb);
        dfsP(root.right, sb);
    }

    public static void dfsM (Node root, StringBuilder sb){
        if(root == null){return;}

        dfsM(root.left, sb);
        sb.append(root.val);
        sb.append(' ');
        dfsM(root.right, sb);
    }

    private static Node copyTree(Node root) {
        if(root == null){return null;}

        Node r = new Node(0);

        r.val = sum(root);

        r.left = copyTree(root.left);
        r.right = copyTree(root.right);

        return r;
    }

    private static int sum (Node root){
        if(root == null){return 0;}
        int sum = 0;
        if (root.left != null) {
            sum += root.left.val;
        }
        if (root.right != null) {
            sum += root.right.val;
        }

        sum += sum(root.left);
        sum += sum(root.right);

        return sum;
    }

    public static Node build (int preIndex, int ml, int mr) {
        if (ml > mr) return null;
        int val = pre[preIndex]; // 目标值

        Node root = new Node(val);

        Map<Integer, Integer> map = new HashMap<>();

        // 在中序中找到目标值
        for (int i = ml; i <= mr; i++) {
            if (mid[i] == val) {
                boolean is = true;
                for (int j = preIndex + 1; j < preIndex + (i - ml) + 1; j++) {
                    if (!map.containsKey(pre[j]) || map.get(pre[j]) < 0) {
                        is = false;
                        break;
                    }

                    map.put(pre[j], map.get(pre[j]) - 1);
                }
                if (!is) continue;
                root.left = build( preIndex + 1, ml, i - 1);
                root.right = build( preIndex + (i - ml) + 1, i + 1, mr);
            } else {
                // 左子树应该出现的值
                if (map.containsKey(mid[i])) {
                    map.put(mid[i], map.get(mid[i]) + 1);
                } else {
                    map.put(mid[i], 1);
                }
            }
        }

        return root;
    }


}
